#include <iostream>
#include <list>
#include <unordered_map>

// void splice (iterator position, list& x);	
// void splice (iterator position, list& x, iterator i);
// void splice (iterator position, list& x, iterator first, iterator last);

class LRUCache
{
private:
    typedef std::list<std::pair<int, int>>::iterator iter;
    std::list<std::pair<int, int>> _LRUList;
    std::unordered_map<int, iter> _hashMap;
    int _capacity;

public:
    LRUCache(int capacity) : _capacity(capacity) {}

    int get(int key)
    {
        auto ret = _hashMap.find(key);
        if (ret == _hashMap.end())
            return -1;

        auto it = ret->second;
        _LRUList.splice(_LRUList.begin(), _LRUList, it);
        return it->second;
    }

    void put(int key, int value)
    {
        auto ret = _hashMap.find(key);
        if (ret != _hashMap.end())
        {
            auto it = ret->second;
            it->second = value;

            _LRUList.splice(_LRUList.begin(), _LRUList, it);
        }
        else
        {
            if (_LRUList.size() == _capacity)
            {
                _hashMap.erase(_LRUList.back().first);
                _LRUList.pop_back();
            }
            _LRUList.push_front({key, value});
            _hashMap[key] = _LRUList.begin();
        }
    }
};
